Day 21 ~ Day 26 我們討論了如何將資料分散到不同節點的 Replication，對那些大型資料集或超大的查詢吞吐量來說，只用 Replication 是沒有效率的，我們需要把資料切成小塊，這個動作稱為 partitions 或 sharding。

partitions 通常是定義如何把資料切成小塊的方法，所有的小塊都屬於每一筆 row、document 或 record，做 partition 最主要的目的就是 scalability (Day 3 或 Day 20)，將 partition 分散到多個節點後，每一個 query 都能獨立進行，所以 query 的吞吐量也能隨著節點的增加而提高。

Partitioning and Replication

partition 通常會隨著 replication 一起做，一個節點會儲存許多不同的 partition，如果我們使用 base-leader 這個 replication 模型，組合 partition 後資料流看起來會如下圖：

每一個節點都能為 partition 的 leader 或 follower，其中做的事情就全部跟 Day 21 ~ Day 26 討論的 Replication 一樣，因為 partition 的 schema 是獨立於 replication schema 的，所以往後幾天再討論 partition 時會忽略 replication 的事情。

Partitioning of Key-Value Data

我們該如何決定哪些資料到哪些節點上呢？

我們的目標是要把資料平均的分配到各節點上以利查詢時能平均查，理論上來看， 10 個節點的查詢和寫入速度應該要比單 1 個節點快 10 倍 (請暫時忽略 replication的事)，如果做 partition 時不公平，某些節點的 partition 資料量或查詢量比其他節點大很多，我們稱之為 skewed (偏斜) ；以最極限的例子來看，所有的流量最終只會查 1 個節點的 partition，其他 9 台很閒，1 個有著高流量的 partition 我們稱之為 hot spot。

一個最簡單避免 hot spot 的方法就是把資料隨機放，雖然節點的資料平均了，但缺點是你不知道資料在哪裡，意味者若要查詢特定 key 資料，你得去查所有節點的 partition。

在來會介紹 2 種更好、更實際的方法。

Partitioning by Key Range

首先第一種方法就是用 key 的範圍做 partition (從 key 的最小值到最大值)，就像下圖那樣，每一本百科全書都用首字字母分開放。

key 的範圍不用平均，因為你的資料本來就不會平均，試想這個百科全書的例子，若將字母以 2 個字母來平均分的話，T ~ Z 這區間的書會很少，這個 partition 的邊界需要以資料做調整。

對於每個 partition 中的資料，我們可以保持 key 為排序的狀態，例如 LSM-Tree (Day 9)，這個好處就是做範圍查詢非常快；然而，它的缺點就是某些操作會讓 partition hot spot，舉例來說你現在需要存感應器的資料，key 為 timestamp，partition 為日，感應器只會在檢測到某些事情時才存資料，所以你可能會有非常大量資料的 partition。

避免的方式就是用別的資訊當做第一個 key，例如感應器的名字，所以在做 partition 時會先用名字分，然後在用 timestamp。

Partitioning by Hash of Key

第二種做 partition 方法就是對 key 做 hash，因為是給 partition 用的 hash，所以我們的安全性不用太講究，例如 Cassandra 和 MongoDB 皆使用 MD5 做為 hash 函式；許多的程式語言皆有內建 hash 函式，要留意的是這些可能不是這麼適合做 partition，例如 Java 的 Object.hashCode() 在某些目的下相同的 key 會有不同的 hash 值。

一個好的 hash 函式可讓資料平均分佈，如下示意圖：

這個 partition 邊界就會很平均了，但有一好就有一壞，這個 partition 方法會損失範圍查詢的效率，因為 key 的排序消失了。

Cassandra 用 compound primary key 的方式來達到一種平衡，Cassandra 只 hash 第一個 key 來做 partition，然後用其他的 key 以 concatenated index 方式做 SSTables 中的排序，這個在一對多 (Day 4) 的資料關係上好處尤其明顯，例如在一個社群網站，每一個 user 有許多貼文，此時若你貼文的 key 選擇 [user_id, update_timestamp]，你就能非常快速的查找某個 user 且也能快速的做時間範圍查詢。

Skewed Workloads and Relieving Hot Spots

講了這麼多我們還得要談談極端例子，即使你使用 key 的 hash 做 partition，還是有可能所有的查詢跟寫入都是同一個 key，所以就會發生 skewed 和 hot spot，以我們網路媒體來舉例，重大新聞發生時，user 都只會看那新聞，其他新聞沒興趣，該新聞的 partition 就會發生大量寫入和查詢。

直到今日，大多數的資料系統並不會自動偵測且補償 skewed 工作量，所以應用程式端得有責任做這些處理，但要留意的是你讓在寫入時的 partition 平均了，可能會順勢拉高查詢時間，例如上面那個新聞事件，我們可以在那新聞 ID 上加上 0～99 的數字，但你查詢時就得要多查 100 個 partition。

老話一句，依舊需要依不同應用軟體的場景做權衡，一定會有某種平衡的方法適合你公司 (例如只加 5 個數字)。